1. Field of the Invention
The field of the invention is that of binary encoding, namely the representation of data of any nature by means of binary elements 0 or 1.
The invention relates notably but not exclusively to the encoding of data designed to be shown sequentially in a pre-established order.
More generally, the invention can be applied in a preferred way when it is necessary to encode data elements which, on an average, appear a substantially equal number of times.
A particular example of application is thus the encoding of a counter for which the data elements to be encoded are integers or whole numbers from 0 to n-1. Besides, counters can always be reduced to this case since, for this purpose, it is enough to number the data elements to be represented from 0 to n-1 in the order in which they appear. The invention can be applied both to simple, systematically incremented counters and to counters that can be sometimes incremented and sometimes decremented.
The invention can be used notably when implementing memories of the type sensitive to wear. This is the case, for example, of E2PROM memories such as those contained in microprocessor cards.
However, it is clear that the invention can be applied to the encoding of any type of data, irrespectively of the type of system and/or data processing and storage media used.
2. Field of the Invention
There are already many known methods for the binary encoding of whole numbers. The method most frequently used consists in representing this whole number by its binary decomposition into a number system using base two. This method is often known as standard binary encoding or natural binary encoding. In another well-known method, each digit of the decomposition of this whole number, in a system using base ten, is represented by the decomposition of this digit into a number system using base two. Four binary elements are then needed to encode each digit of the decomposition in the base ten system. There are again several types of binary encodings, corresponding to specific applications or needs.
Thus, in certain applications, it is desirable that the encoding method used should be such that when changing from one whole number to the next whole number, or to the preceding whole number, the number of binary elements that change value is as small as possible on an average, the ideal being 1. Standard binary encoding falls far short of this ideal, since the average number is equal to about 2.
Satisfactory approaches to this minimum change constraint have long existed. These approaches are known as minimum-change codes and are described, for example, in W. R. Bennet & J. R. Davey, Data Transmission, New York, McGraw Hill, 1965. The Gray codes constitute a particular example of minimum-change codes. They are notably described in the U.S. patent published on Mar. 17 1953 under No. 2,632,058.
The Gray codes have proved to be particularly valuable and are much used owing to the simplicity of their construction and the simplicity of the conversions between these codes and the standard binary code and because the number of binary elements used is equal to the number of binary elements used in the standard binary encoding, said number being as small as possible.
However, it is sometimes also desirable for all the binary elements to change value, on an average, as much as one another, i.e. it is desirable for the change to be uniform. Gray encoding does not have this property since a binary element of low significance changes a number of times equal to half the whole numbers to be encoded at each cycle of a counter while the binary element of high significance changes only once.
The constraint of uniform changing of the binary elements arises, for example, in a crucial way in the case of E2PROM type memories. For, in these memories, since the number of instances of changing possible for each binary element is limited (for example it is in the range of some thousands) it is advantageous to distribute the changings homogeneously among all the binary elements, thus enabling the lifetime of the components to be prolonged.
There is no encoding that is truly effective with respect to this particular constraint.